动态规划 |
您所在的位置：网站首页 › 最大连续子数组和 动态规划java › 动态规划 |
动态规划
|
动态规划——最大子序和
1.问题描述
给定一个整数数组nums,找到一个具有最大连续子数组（子数组最少包含一个元素），返回其最大和。 示例 输入：[-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组[4,-1,2,1]的和最大为6 2.要求（1）写出问题分析的过程 （2）写出程序代码 （3）贴出程序结果 实验过程（1）分析过程 利用动态规划来解决，即可以通过一次遍历完成对最大子序列以及相应位置坐标的求解。 步骤一：令状态dp[i]表示A[i]作为连续序列的最大和（这里所说A[i]必须作为连续序列的末尾）。 步骤二：作如下考虑：因为dp[i]要求必须以A[i]结尾，那么有两种情况： 1.这个最大序列连续序列只有一个元素，即A[i] 2.有多个元素时，即从前某处A[p]开始，一直到A[i]结尾 对于第一种情况，最大和就是A[i]本身、 对于第二种情况，最大和就是dp[i-1]+A[i] 于是就得到状态方程：dp[i-1]=max{A[i]，dp[i-1]+A[i]} 这个式子只和i与i之前的元素有关，且边界为dp[0]=A[0]，由此从小到大枚举i，既可以得到整个数组。接着输出数组dp中最大的数值即最大连续子序列的和。 （2）程序代码 package ch01; import java.util.Scanner; public class zuidahelianxuxulie { static int maxn=10010; //求较大值 public static int max(int a,int b) { return a>b?a:b; } public static void main(String[] args) { Scanner scanner =new Scanner(System.in); System.out.println("请输入数组的个数："); int n=scanner.nextInt(); int [] A =new int [maxn]; System.out.println("请输入数组："); for(int i=0;i //状态转方程 dp[i]=max(A[i], dp[i-1]+A[i]); } //求最大连续子序列和 int k; k=dp[0]; for(int i=1;i k=dp[i]; } } System.out.println("最大和连续序列为:"+k); return; } }（3）运行结果 |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |